package structure.array;


import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 地址：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/
 * <p>
 * 题目：剑指 Offer 57. 和为s的两个数字
 * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[2,7] 或者 [7,2]
 * 示例 2：
 * <p>
 * 输入：nums = [10,26,30,31,47,60], target = 40
 * 输出：[10,30] 或者 [30,10]
 */
public class Leetcode_Sword_Offer_57 {
    public static void main(String[] args) {

        int[] input = new int[]{2, 7, 11, 15};
        int[] input1 = new int[]{10, 26, 30, 31, 47, 60};

        int[] ints = twoSum(input, 9);
        for (int anInt : ints) {
            System.out.println(anInt);
        }

        System.out.println("-----");

        int[] ints1 = twoSum(input1, 40);
        for (int anInt : ints1) {
            System.out.println(anInt);
        }

    }


    /**
     * 解法1：
     * 思路： 利用递增的特性，双指针，左指针和有指针
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * <p>
     * 执行结果：通过
     * 执行用时：2 ms, 在所有 Java 提交中击败了92.65%的用户
     * 内存消耗：55 MB, 在所有 Java 提交中击败了86.36%的用户
     * <p>
     * 可以优化的地方在哪里？
     *
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        while (start < end) {
            if (target - nums[start] == nums[end]) {
                return new int[]{nums[start], nums[end]};
            } else if (nums[start] + nums[end] > target) {
                end--;
            } else {
                start++;
            }
        }
        return new int[]{-1, -1};
    }
}
